package com.zang.greedy;

/**
 * @author Cizai
 * @since 2022/11/28 19:07
 * @see <a href="https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-cooldown/">...</a>
 **/
public class 最佳买卖股票的时机含冷冻期 {

    // 三种状态分别为手上没有股票的时候，手上持有股票的时候，还有冷却期
    public int maxProfit(int[] prices) {

        int len = prices.length;
        int[][] dp = new int[len][3];
        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        dp[0][2] = 0;

        for (int i = 1; i < len; i++) {
            // 这次仔细写一下状态转移方程
            // 在没有持有股票的时候肯定是上一次没有，或者在冷却期
            dp[i][0] = Math.max(dp[i-1][0],dp[i-1][2]);
            // 在持有股票的时候可能上一次就持有，或者上一次没有这次买入了
            dp[i][1] = Math.max(dp[i-1][1],dp[i-1][0]-prices[i]);
            // 股票冷却只有一种情况就是上一条卖出了
            dp[i][2] = dp[i-1][1] + prices[i];
        }
        // 最高的时候只可能是最后一天不持有或者进入了冷却期的时候
        return Math.max(dp[len-1][0],dp[len-1][2]);
    }
}
